package linkedlist;

/**
 * @author cxyxj
 */
public class MyDoubleLinkedList {
    /**
     * 头节点
     */
    MyDoubleNode headNode;
    /**
     * 尾节点
     */
    MyDoubleNode tailNode;
    /**
     * 节点的个数
     */
    int size;

    private static class MyDoubleNode {
        /**
         * 值
         */
        String item;
        /**
         * 下一个节点的指针
         */
        MyDoubleNode next;
        /**
         * 上一个节点的指针
         */
        MyDoubleNode prev;

        MyDoubleNode(MyDoubleNode prev, String data, MyDoubleNode next) {
            this.item = data;
            this.next = next;
            this.prev = prev;
        }
    }

    public void print() {
        MyDoubleNode cur = headNode;
        while(cur != null) {
            System.out.println(cur.item + " ");
            cur = cur.next;
        }
    }

    /**
     * 添加节点到头部
     */
    public void addHead(String data) {
        MyDoubleNode head = headNode;
        //在头节点插入元素，上一个元素的指针肯定是 null 的
        MyDoubleNode newNode = new MyDoubleNode(null, data, head);
        //head 为 null，代表链表中没有元素
        if(head == null) {
            //尾节点也是新节点
            tailNode = newNode;
        } else {
            //prev 指向新节点
            head.prev = newNode;
        }
        //将新节点做为头节点
        headNode = newNode;
        size++;
    }

    /**
     * 添加节点到链表尾部
     */
    public void add(String data) {
        MyDoubleNode tail = tailNode;
        MyDoubleNode newNode = new MyDoubleNode(tail, data, null);
        tailNode = newNode;
        if(tail == null) {
            headNode = newNode;
        } else {
            tail.next = newNode;
        }
        size++;
    }

    /**
     * 指定下标添加链表节点
     */
    public void add(int index, String data) {
        //下标越界
        if(index > size || index < 0) {
            throw new IndexOutOfBoundsException("Index: " + index +
                    ", Size: " + size);
        }
        //如果添加的是尾部元素
        if(index == size) {
            add(data);
        } else {
            //获得指定下标节点
            MyDoubleNode node = getNode(index);
            //获得下标节点的上个节点
            MyDoubleNode prev = node.prev;
            //构建新节点 新节点已经关联了上一个节点和下一个节点关系 只需要再关联 上一个节点和下一个节点 与新节点的关系
            MyDoubleNode newNode = new MyDoubleNode(prev, data, node);
            //将下标节点的上个指针指向新节点
            node.prev = newNode;
            //当 index 为 0 时，prev 是为 null 的，也就是添加头节点
            //将新节点给 headNode
            if(prev == null) {
                headNode = newNode;
            } else {
                //将下标节点的上个节点的 next 指针指向新节点
                prev.next = newNode;
            }
            size++;
        }
    }

    //这个获得指定下标的元素的代码是可以进行优化的
//各位小伙伴可以去看看 LinkedList 的实现
    private MyDoubleNode getNode(int index) {
        //由于有了上一个元素的指针，可以从后向前遍历
        MyDoubleNode cur = headNode;
        for(int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 删除指定下标节点
     */
    public void remove(int index) {
        //下标越界
        if(index >= size || index < 0) {
            throw new IndexOutOfBoundsException("Index: " + index +
                    ", Size: " + size);
        }
        MyDoubleNode node = getNode(index);
        MyDoubleNode prev = node.prev;
        MyDoubleNode next = node.next;
        // prev 为 null，代表 index = 0
        // 将要删除节点的下一个节点作为 headNode
        if(prev == null) {
            headNode = next;
        } else {
            //跳过要删除节点的指向， 将要删除节点的上一个节点 指向 要删除节点的下一个节点
            prev.next = next;
            //方便GC
            node.prev = null;
        }
        // next 为 null，代表 index 为最大的下标，也就是要删除尾部节点
        // 将要删除节点的上一个节点作为 tailNode
        if(next == null) {
            tailNode = prev;
        } else {
            //跳过要删除节点的指向， 将要删除节点的下一个节点 指向 要删除节点的上一个节点
            next.prev = prev;
            //方便GC
            node.next = null;
        }
        node.item = null;
        size--;
    }

    /**
     * 删除链表头节点
     */
    private void removeHead() {
        //remove(0);
        if(headNode == null) {
            return;
        }
        //获得头节点的下个节点
        MyDoubleNode headNext = headNode.next;
        //方便GC
        headNode.item = null;
        headNode.next = null;

        //将下个节点赋值给头节点
        headNode = headNext;
        //如果头节点的下个节点为 null，说明链表中就一个节点
        //删除了这个节点，尾节点也要为 null
        if(headNext == null) {
            tailNode = null;
        } else {
            //链表中有多个节点，headNext 现在为 头节点，头节点的 prev 指针需要指向 null
            headNext.prev = null;
        }
        size--;
    }

    /**
     * 删除链表尾节点
     */
    public void removeTail() {
        // remove(size -1);
        if(tailNode == null) {
            return;
        }
        //获得尾节点的上个节点
        MyDoubleNode tailPrev = tailNode.prev;
        //方便GC
        tailNode.item = null;
        tailNode.prev = null;
        //将上个节点赋值给尾节点
        tailNode = tailPrev;
        //如果尾节点的上个节点为 null，说明链表中就一个节点
        //删除了这个节点，头节点也要为 null
        if(tailPrev == null) {
            headNode = null;
        } else {
            //链表中有多个节点，tailPrev 现在为尾节点，尾节点的 next 指针需要指向 null
            tailPrev.next = null;
        }
        size--;
    }

    /**
     * 修改指定下标节点值
     */
    public void set(int index, String data) {
        //下标越界
        if(index >= size || index < 0) {
            throw new IndexOutOfBoundsException("Index: " + index +
                    ", Size: " + size);
        }
        //获得指定下标节点
        MyDoubleNode node = getNode(index);
        node.item = data;
    }

    /**
     * 获得指定下标节点的值
     */
    public String get(int index) {
        //下标越界
        if(index >= size || index < 0) {
            throw new IndexOutOfBoundsException("Index: " + index +
                    ", Size: " + size);
        }
        //获得指定下标节点
        MyDoubleNode node = getNode(index);
        return node.item;
    }

    public static void main(String[] args) {

        MyDoubleLinkedList linkedList = new MyDoubleLinkedList();

        System.out.println("添加到头部");
        linkedList.addHead("22");
        linkedList.addHead("11");
        linkedList.print();
        System.out.println("添加到尾部");
        linkedList.add("33");
        linkedList.print();
        System.out.println("指定下标添加");
        linkedList.add(0,"555");
        linkedList.add(2,"55544");
        linkedList.add(5,"666");
        linkedList.print();
        System.out.println("指定下标删除");

        linkedList.remove(1);
        linkedList.remove(1);

        linkedList.print();
        System.out.println("删除头尾节点");
        linkedList.removeHead();
        linkedList.removeTail();
        linkedList.print();
        System.out.println("指定下标修改节点");
        linkedList.set(0,"cxyxj");
        linkedList.print();
        System.out.println("获得指定下标节点");
        System.out.println(linkedList.get(0));
    }
}
